//图
#ifndef __GRAPH__HPP
#define __GRAPH__HPP

#include"../Universal.h"
#include"../Queue/LinkedQueue.hpp"
#include"../Queue/PriorityQueue.hpp"
#include"../Stack/DynamicStack.hpp"
#include"../LinkedList/StaticList.hpp"
#include"../Tree/Tree.hpp"

namespace NgSiuKei {

template<class Val, class Weights>
class Graph {
    public:
    Graph(void);
    ~Graph(void);

    public:
    //清空
    void clean(void);
    //查找
    bool findVal(const Val val);
    //插入
    void insertVal(const Val val);
    //删除
    void deleteVal(const Val val);
    //查找路径
    bool findEdge(const Val tailVal, const Val headVal, const Weights weights, const GraphRoadType type);
    bool findEdge(const Val tailVal, const Val headVal, const GraphRoadType type);
    //获取路径权重
    Weights getEdgeWidghts(const Val tailVal, const Val headVal);
    //设置路径
    void setEdge(const Val tailVal, const Val headVal, const Weights weights, const GraphRoadType type);
    //删除路径
    void deleteEdge(const Val tailVal, const Val headVal, const GraphRoadType type);
    //获取图类型
    GraphType getType(void);
    //是否有向
    bool isDirected(void);
    //是否有权
    bool isWeightsGraph(void);
    //是否连通图
    bool isConnectivity(void);
    //是否有回路
    bool haveCycle(void);
    //是不是二部图
    bool isBipartite(void);
    bool isBipartite(Val **outputU, U_L_L *outputUSize, Val **outputV, U_L_L *outputVSize);
    //获取某个节点到另一个节点的最短路径（返回：<路径[endVal...startVal], Weights>）
    pair<DynamicStack<Val>*, Weights> getShortestPaths(const Val startVal, const Val endVal, bool isIgnoreWeights = false);
    //获取目标值为根节点的最小生成树
    tree_node<Val> *getMinSpanningTree(Val rootVal, GetMinSpanningTreeFuncType type = GetMinSpanningTreeFuncTypePrim);
    //获取最大流通量
    Weights getMaximunFlow(const Val startVal, const Val endVal, const GetMaximunFlowFuncType type = GetMaximunFlowFuncTypeNormal);
    //获取最小割，<S集，T集，最小割值>
    tuple<PriorityQueue<Val> *, PriorityQueue<Val> *, Weights> getMinCut(const Val startVal, const Val endVal);
    //获取最大匹配
    Weights getMaxMatching(Val *U, U_L_L uSize, Val *V, U_L_L vSize);
    //获取稳定婚配结果（结果相对于woman，man会得到更让他们满意的匹配结果）
    LinkedQueue<pair<Val, Val>> *getStableMarriage(Val *mans, LinkedQueue<Val> *mansLike, U_L_L manNum, Val *womans, StaticList<Val> *womansLike, U_L_L womanNum);
    //打印
    void print(void);

    private:
    //获取Val下标
    U_L_L getValIndex(const Val val);
    //获取某个节点到所有节点的最短路径
    tuple<Val, Val, bool, Weights> *getAllShortestPaths(const Val val, bool isIgnoreWeights);
    tuple<Val, Val, bool, Weights> *getAllShortestPathsInUnweightedGraph(const Val val);  //用于无权图
    tuple<Val, Val, bool, Weights> *getAllShortestPathsInWeightedGraph(const Val val);    //用于有权图（Dijkstra算法）
    //获取最小生成树的算法
    tree_node<Val> *prim(Val rootVal);
    tree_node<Val> *kruskal(Val rootVal);
    //获取最大流通量的算法
    Weights getMaxFlowFuncTypeNormal(const Val startVal, const Val endVal); //普通的垃圾算法，有可能获取不到
    Weights getMaxFlowFuncTypeFordFulkerson(const Val startVal, const Val endVal, PriorityQueue<Val> *S = nullptr); //Ford-Fulkerson算法（S为了给getMinCut用）
    Weights getMaxFlowFuncTypeEdmondsKarp(const Val startVal, const Val endVal); //Edmonds-Karp算法
    Weights getMaxFlowFuncTypeDinic(const Val startVal, const Val endVal); //Dinic's算法
    //最大匹配算法
    Weights MCBM(Val *U, U_L_L uSize, Val *V, U_L_L vSize); //用于无权二部图，不知道叫啥名字所以用问题的缩写代替（Maximum Cardinality Bipartite Matching）
    Weights hungarian(Val *U, U_L_L uSize, Val *V, U_L_L vSize, bool getMax = true); //匈牙利算法（getMax:true-最大匹配;false-最小匹配）(#这个匈牙利算法和网上找到的大部分“匈牙利算法”不同，我坚持王树森和网站[https://www.hungarianalgorithm.com/index.php]所演示的算法为匈牙利算法)
    //解决稳定婚配问题的算法
    LinkedQueue<pair<Val, Val>> *GaleShapley(Val *mans, LinkedQueue<Val> *mansLike, U_L_L manNum, Val *womans, StaticList<Val> *womansLike, U_L_L womanNum);

    private:
    U_L_L size; //节点数量
    Val vals[MAX_SIZE]; //节点列表
    bool edges[MAX_SIZE][MAX_SIZE]; //边邻接列表
    Weights edgesWeights[MAX_SIZE][MAX_SIZE]; //边权重邻接列表
};

template<class Val, class Weights>
Graph<Val, Weights>::Graph(void) {
    this->size = 0;
    for(U_L_L i=0; i<MAX_SIZE; ++i) {
        for(U_L_L j=0; j<MAX_SIZE; ++j) {
            this->edges[i][j] = false;
            this->edgesWeights[i][j] = Unweighted;
        }
    }
}

template<class Val, class Weights>
Graph<Val, Weights>::~Graph(void) {

}

template<class Val, class Weights>
void Graph<Val, Weights>::clean(void) {
    this->size = 0;
    for(U_L_L i=0; i<MAX_SIZE; ++i) {
        for(U_L_L j=0; j<MAX_SIZE; ++j) {
            this->edges[i][j] = false;
            this->edgesWeights[i][j] = Unweighted;
        }
    }
}

template<class Val, class Weights>
bool Graph<Val, Weights>::findVal(const Val val) {
    for(U_L_L i=0; i<this->size; ++i) {
        if(this->vals[i] == val) {
            return true;
        }
    }
    return false;
}

template<class Val, class Weights>
void Graph<Val, Weights>::insertVal(const Val val) {
    if(this->findVal(val) || this->size == MAX_SIZE) {
        return;
    }

    this->vals[this->size] = val;
    ++this->size;
}

template<class Val, class Weights>
void Graph<Val, Weights>::deleteVal(const Val val) {
    if(0 == this->size || !this->findVal(val)) {
        return;
    }

    //删除的地方自己画图理解吧
    U_L_L index = 0;
    while(index < this->size && val != this->vals[index]) {index++;}
    if(index>=this->size) {return;}
    for(U_L_L i=index; i<this->size-1; ++i) {
        this->vals[i] = this->vals[i+1];
    }
    for(U_L_L i=0; i<this->size-1; ++i) {
        for(U_L_L j=0; j<this->size-1; ++j) {
            if(i == j || (i < index && j < index)) {
                continue;
            }
            if(index > i) {
                this->edges[i][j] = this->edges[i][j+1];
            }
            else if(index > j) {
                this->edges[i][j] = this->edges[i+1][j];
            }
            else {
                this->edges[i][j] = this->edges[i+1][j+1];
            }
        }
    }
    --this->size;
}

//查找路径
template<class Val, class Weights>
bool Graph<Val, Weights>::findEdge(const Val tailVal, const Val headVal, const Weights weights, const GraphRoadType type) {
    if(!this->findVal(tailVal) || !this->findVal(headVal)) {
        return false;
    }
    
    U_L_L tailIndex = this->getValIndex(tailVal), headIndex = this->getValIndex(headVal);
    if(type == GraphRoadTypeDirected) {
        if(this->edges[tailIndex][headIndex] && weights == this->edgesWeights[tailIndex][headIndex]) {
            return true;
        }
    }
    else {
        if(this->edges[tailIndex][headIndex] && weights == this->edgesWeights[tailIndex][headIndex] &&
            this->edges[headIndex][tailIndex] && weights == this->edgesWeights[headIndex][tailIndex]) {
            return true;
        }
    }
    return false;
}

template<class Val, class Weights>
bool Graph<Val, Weights>::findEdge(const Val tailVal, const Val headVal, const GraphRoadType type) {
    if(!this->findVal(tailVal) || !this->findVal(headVal)) {
        return false;
    }
    
    U_L_L tailIndex = this->getValIndex(tailVal), headIndex = this->getValIndex(headVal);
    if(type == GraphRoadTypeDirected) {
        if(this->edges[tailIndex][headIndex]) {
            return true;
        }
    }
    else {
        if(this->edges[tailIndex][headIndex] && this->edges[headIndex][tailIndex]) {
            return true;
        }
    }
    return false;
}

//获取路径权重
template<class Val, class Weights>
Weights Graph<Val, Weights>::getEdgeWidghts(const Val tailVal, const Val headVal) {
    Weights result = 0;
    if(this->findVal(tailVal) && this->findVal(headVal)) {
        U_L_L tailValIndex = this->getValIndex(tailVal);
        U_L_L headValIndex = this->getValIndex(headVal);
        if(this->edges[tailValIndex][headValIndex]) {
            result = this->edgesWeights[tailValIndex][headValIndex];
        }
    }
    return result;    
}

//设置路径
template<class Val, class Weights>
void Graph<Val, Weights>::setEdge(const Val tailVal, const Val headVal, const Weights weights, const GraphRoadType type) {
    if(!this->findVal(tailVal) || !this->findVal(headVal) || tailVal == headVal) {
        return;
    }

    U_L_L tailIndex = this->getValIndex(tailVal), headIndex = this->getValIndex(headVal);
    if(type == GraphRoadTypeDirected && Unweighted != weights) {
        this->edgesWeights[tailIndex][headIndex] = weights;
        this->edges[tailIndex][headIndex] = true;
    }
    else {
        this->edgesWeights[tailIndex][headIndex] = weights;
        this->edgesWeights[headIndex][tailIndex] = weights;
        this->edges[tailIndex][headIndex] = true;
        this->edges[headIndex][tailIndex] = true;
    }
}


//删除路径
template<class Val, class Weights>
void Graph<Val, Weights>::deleteEdge(const Val tailVal, const Val headVal, const GraphRoadType type) {
    if(!this->findVal(tailVal) || !this->findVal(headVal)) {
        return;
    }

    U_L_L tailIndex = this->getValIndex(tailVal), headIndex = this->getValIndex(headVal);
    if(type == GraphRoadTypeDirected) {
        this->edges[tailIndex][headIndex] = false;
    }
    else {
        this->edges[tailIndex][headIndex] = false;
        this->edges[headIndex][tailIndex] = false;
    }
}

//获取图类型
template<class Val, class Weights>
GraphType Graph<Val, Weights>::getType(void) {
    if(2 > this->size) {
        return GraphTypeUndirectedAndUnweighted;
    }
    int type = 0;
    U_L_L i, j;

    for(i=0; i<this->size; ++i) {
        for(j=0; j<i; ++j) {
            if(this->edges[i][j] != this->edges[j][i]) { //不是双向即为有向
                type = type | 10;
            }
            else if(this->edges[i][j] &&
                    this->edges[j][i] &&
                    this->edgesWeights[i][j] != this->edgesWeights[j][i]) { //双向但权不同即为有向有权
                type = type | 10;
                type = type | 1;
            }
            if((this->edges[i][j] && Unweighted != this->edgesWeights[i][j]) ||
                (this->edges[j][i] && Unweighted != this->edgesWeights[j][i])) { //有权
                type = type | 1;
            }
        }
    }
    return (GraphType)type;
}

//是否有向
template<class Val, class Weights>
bool Graph<Val, Weights>::isDirected(void) {
    GraphType type = this->getType();
    return GraphTypeDirectedAndUnweighted == type || GraphTypeDirectedAndWeighted == type;
}

//是否有权
template<class Val, class Weights>
bool Graph<Val, Weights>::isWeightsGraph(void) {
    GraphType type = this->getType();
    return GraphTypeUndirectedAndWeighted == type || GraphTypeDirectedAndWeighted == type;
}

//是否连通图
template<class Val, class Weights>
bool Graph<Val, Weights>::isConnectivity(void) {
    if(this->size < 2) {
        return true;
    }

    U_L_L i, j;
    Val currentVal;
    U_L_L currentValIndex;
    LinkedQueue<Val> queue;
    bool visited[this->size];

    //任一点到任一点都有至少一条路径为连通
    for(j=0; j<this->size; ++j) {
        for(i=0; i<this->size; ++i) {
            visited[i] = false;
        }

        currentVal = this->vals[j];
        queue.push(currentVal);
        while(!queue.isEmpty()) {
            currentVal = queue.pop();
            currentValIndex = this->getValIndex(currentVal);
            if(!visited[currentValIndex]) {
                for(i=0; i<this->size; ++i) {
                    if(i == currentValIndex) {
                        continue;
                    }
                    if(this->edges[currentValIndex][i]) {
                        queue.push(this->vals[i]);
                    }
                }
                visited[currentValIndex] = true;
            }
        }

        for(i=0; i<this->size; ++i) {
            if(!visited[i]) {
                return false;
            }
        }
    }
    return true;
}

//是否有回路
template<class Val, class Weights>
bool Graph<Val, Weights>::haveCycle(void) {
    if(this->size < 2) {
        return false;
    }

    U_L_L i, j;
    LinkedQueue<Val> queue;
    bool visited[this->size];
    U_L_L degrees[this->size];
    bool isDirected = this->isDirected();

    for(i=0; i<this->size; ++i) {
        visited[i] = false;
        degrees[i] = 0;
    }

    for(i=0; i<this->size; ++i) {
        for(j=0; j<this->size; ++j) {
            if(i == j) {
                continue;
            }

            if(this->edges[i][j]) {
                if(!isDirected) {
                    ++degrees[i];
                }
                else {
                    ++degrees[j];
                }
            }
        }
    }

    for(i=0; i<this->size; ++i) {
        if((!isDirected && 1 >= degrees[i]) || (isDirected && 0 == degrees[i])) {
            queue.push(this->vals[i]);
        }
    }

    Val currentVal;
    U_L_L currentValIndex;
    while(!queue.isEmpty()) {
        currentVal = queue.pop();
        currentValIndex = this->getValIndex(currentVal);
        for(i=0; i<this->size; ++i) {
            if(i == currentValIndex) {
                continue;
            }

            if(this->edges[currentValIndex][i]) {
                --degrees[i];
                if((!isDirected && 1 >= degrees[i]) || (isDirected && 0 == degrees[i])) {
                    queue.push(this->vals[i]);
                }
            }
        }
        visited[currentValIndex] = true;
    }

    for(i=0; i<this->size; ++i) {
        if(!visited[i]) {
            return true;
        }
    }
    return false;
}

//是不是二部图
template<class Val, class Weights>
bool Graph<Val, Weights>::isBipartite(void) {
    return this->isBipartite(nullptr, nullptr, nullptr, nullptr);
}

template<class Val, class Weights>
bool Graph<Val, Weights>::isBipartite(Val **outputU, U_L_L *outputUSize, Val **outputV, U_L_L *outputVSize) {   
    if(this->size <= 1 || this->isDirected()) {
        return false;
    }

    int visited[this->size] = {0}; //0-还没遍历;1-红;2-蓝
    LinkedQueue<Val> queue;
    queue.push(this->vals[0]);

    Val currentVal;
    U_L_L i, currentIndex;
    while(!queue.isEmpty()) {
        // queue.print();
        while(!queue.isEmpty()) {
            currentVal = queue.pop();
            currentIndex = this->getValIndex(currentVal);
            if(0 == visited[currentIndex]) {
                visited[currentIndex] = 1;
            }
            for(i=0; i<this->size; ++i) {
                if(i == currentIndex || !this->edges[currentIndex][i]) {
                    continue;
                }

                //如果遍历过了要检测是否和currentVal同色
                if(0 != visited[i]) {
                    if(visited[i] == visited[currentIndex]) {
                        return false;
                    }
                    else {
                        continue;
                    }
                }

                visited[i] = (visited[currentIndex]==1)?(2):(1);
                queue.push(this->vals[i]);
            }
        }
        for(i=0; i<this->size; ++i) {
            if(0 == visited[i]) {
                queue.push(this->vals[i]);
                break;
            }
        }
    }

    if(nullptr != outputU && nullptr != outputUSize && nullptr != outputV && nullptr != outputVSize) {
        LinkedQueue<Val> queueU, queueV;
        for(i=0; i<this->size; ++i) {
            if(1 == visited[i]) {
                queueU.push(this->vals[i]);
            }
            else {
                queueV.push(this->vals[i]);
            }
        }

        *outputUSize = queueU.getSize();
        *outputVSize = queueV.getSize();

        if(nullptr != (*outputU)) {
            delete [](*outputU);
            *outputU = nullptr;
        }
        if(nullptr != (*outputV)) {
            delete [](*outputV);
            *outputV = nullptr;
        }
        *outputU = new Val[*outputUSize];
        *outputV = new Val[*outputVSize];

        for(i=0; i<(*outputUSize); ++i) {
            if(!queueU.isEmpty()) {
                (*outputU)[i] = queueU.pop();
            }
        }
        for(i=0; i<(*outputVSize); ++i) {
            if(!queueV.isEmpty()) {
                (*outputV)[i] = queueV.pop();
            }
        }
    }

    return true;
}

//获取某个节点到另一个节点的最短路径，返回：<路径[endVal...startVal], 路径权重>
template<class Val, class Weights>
pair<DynamicStack<Val>*, Weights> Graph<Val, Weights>::getShortestPaths(const Val startVal, const Val endVal, bool isIgnoreWeights) {
    tuple<Val, Val, bool, Weights> *paths = getAllShortestPaths(startVal, isIgnoreWeights);
    if(nullptr == paths) {
        return make_pair(new DynamicStack<Val>, Unweighted);
    }
    Weights weight = Unweighted;
    DynamicStack<Val> *stack = new DynamicStack<Val>;
    tuple<Val, Val, bool, Weights> shortestPath = paths[this->getValIndex(endVal)];
    if(get<2>(shortestPath)) {//存在该路径
        weight = get<3>(shortestPath);
        Val currentVal = endVal;
        Val lastVal;
        while(currentVal != startVal) {
            stack->push(currentVal);
            lastVal = get<1>(paths[this->getValIndex(currentVal)]);
            currentVal = get<0>(paths[this->getValIndex(lastVal)]);
        }
        stack->push(startVal);
    }
    delete paths;
    return make_pair(stack, weight);
}

//获取目标值为根节点的最小生成树
template<class Val, class Weights>
tree_node<Val> *Graph<Val, Weights>::getMinSpanningTree(Val rootVal, GetMinSpanningTreeFuncType type) {
    if(0 == this->size || this->isDirected() || !this->findVal(rootVal) || !this->isConnectivity()) {
        //1、空图
        //2、有向
        //3、没有目标节点
        //4、不是连通图
        return nullptr;
    }

    tree_node<Val> *minSpanningTree = nullptr;
    switch(type) {
        case GetMinSpanningTreeFuncTypePrim: {
            minSpanningTree = this->prim(rootVal);
            break;
        }
        case GetMinSpanningTreeFuncTypeKruskal: {
            minSpanningTree = this->kruskal(rootVal);
            break;
        }
        default: {
            break;
        }
    }
    return minSpanningTree;
}

//获取最大流通量
template<class Val, class Weights>
Weights Graph<Val, Weights>::getMaximunFlow(const Val startVal, const Val endVal, const GetMaximunFlowFuncType type) {
    if(GraphTypeDirectedAndWeighted != this->getType() || !(this->findVal(startVal) && this->findVal(endVal))) {
        return Unweighted;
    }

    U_L_L startValIndex = this->getValIndex(startVal);
    U_L_L endValIndex = this->getValIndex(endVal);
    pair<DynamicStack<Val>*, Weights> road = this->getShortestPaths(startVal, endVal);
    if(nullptr != road.first) { //起点无法到达终点就啥都不用聊了
        delete road.first;
        switch(type) {
            case GetMaximunFlowFuncTypeNormal: {
                return this->getMaxFlowFuncTypeNormal(startVal, endVal);
                break;
            }
            case GetMaximunFlowFuncTypeFordFulkerson: {
                return this->getMaxFlowFuncTypeFordFulkerson(startVal, endVal);
                break;
            }
            case GetMaximunFlowTypeEdmondsKarp: {
                return this->getMaxFlowFuncTypeEdmondsKarp(startVal, endVal);
                break;
            }
            case GetMaximunFlowTypeDinic: {
                return this->getMaxFlowFuncTypeDinic(startVal, endVal);
                break;
            }
            default: {
                break;
            }
        }
    }
    return Unweighted;
}

//获取最小割，<S集，T集，最小割值>
template<class Val, class Weights>
tuple<PriorityQueue<Val> *, PriorityQueue<Val> *, Weights> Graph<Val, Weights>::getMinCut(const Val startVal, const Val endVal) {
    PriorityQueue<Val> *S = new PriorityQueue<Val>;
    PriorityQueue<Val> *T = new PriorityQueue<Val>;
    PriorityQueue<Val> *tempS = new PriorityQueue<Val>;
    bool visited[this->size];
    Val tempVal;

    Weights minCutWeights = this->getMaxFlowFuncTypeFordFulkerson(startVal, endVal, tempS);
    while(!tempS->isEmpty()) {
        tempVal = tempS->pop();
        visited[this->getValIndex(tempVal)] = true;
        S->push(tempVal);
    }
    for(U_L_L i=0; i<this->size; ++i) {
        if(!visited[i]) {
            T->push(this->vals[i]);
        }
    }

    return make_tuple(S, T, minCutWeights);
}

//打印
template<class Val, class Weights>
//获取最大匹配
Weights Graph<Val, Weights>::getMaxMatching(Val *U, U_L_L uSize, Val *V, U_L_L vSize) {
    if(nullptr == U || nullptr == V || 0 == uSize || 0 == vSize) {
        return Unweighted;
    }

    U_L_L i;
    Weights result = Unweighted;
    if(!this->isBipartite()) {
        return result;
    }
    //这里应该有一套逻辑判断入参和获取的集是否相同的，但是没想到特别好的办法
    // Val *outputU = nullptr;
    // Val *outputV = nullptr;
    // U_L_L outputUSize;
    // U_L_L outputVSize;
    // if(!this->isBipartite(&outputU, &outputUSize, &outputV, &outputVSize)) {
    //     return result;
    // }
    // if(uSize != outputUSize || vSize != outputVSize) {
    //     return result;
    // }
    // else {
    //     for() {

    //     }
    // }
    for(i=0; i < uSize; ++i) {
        if(!this->findVal(U[i])) {
            return result;
        }
    }
    for(i=0; i < vSize; ++i) {
        if(!this->findVal(V[i])) {
            return result;
        }
    }

    if(this->isWeightsGraph()) {
        //使用匈牙利算法
        result = this->hungarian(U, uSize, V, vSize, true);
    }
    else {
        //无权图特定方法
        result = this->MCBM(U, uSize, V, vSize);
    }
    return result;
}


//获取稳定婚配结果
template<class Val, class Weights>
LinkedQueue<pair<Val, Val>> *Graph<Val, Weights>::getStableMarriage(Val *mans, LinkedQueue<Val> *mansLike, U_L_L manNum, Val *womans, StaticList<Val> *womansLike, U_L_L womanNum) {
    if(nullptr == mans || nullptr == womans || nullptr == mansLike || nullptr == womansLike || 0 == manNum || 0 == womanNum) {
        return nullptr;
    }
    return this->GaleShapley(mans, mansLike, manNum, womans, womansLike, womanNum);
}

//打印
template<class Val, class Weights>
void Graph<Val, Weights>::print(void) {
    cout << "val [ ";
    for(U_L_L i=0; i<this->size; ++i) {
        cout << this->vals[i] << ' ';
    }
    cout << ']' << endl;
    
    cout << "edges:" << endl;
    if(this->size < 2) {
        cout << "null" << endl;
    }
    else {
        for(U_L_L i=0; i<this->size; ++i) {
            for(U_L_L j=0; j<this->size; ++j) {
                cout << "[ " << this->vals[i] << " ]->[ " << this->vals[j] << " ] = [ ";
                if(this->edges[i][j]) {
                    cout << this->edgesWeights[i][j] << " ]" << endl;
                }
                else {
                    cout << "null ]" << endl;
                }
            }
        }
    }
    cout << "------------------------------------" << endl;
}

//获取Val下标
template<class Val, class Weights>
U_L_L Graph<Val, Weights>::getValIndex(const Val val) {
    if(!this->findVal(val)) {
        return this->size;
    }
    for(U_L_L i=0; i<this->size; ++i) {
        if(val == this->vals[i]) {
            return i;
        }
    }
    return this->size;
}

//获取某个节点到所有节点的最短路径（返回：<目标节点, 上一个节点, 是否存在路径, 路径权重>
template<class Val, class Weights>
tuple<Val, Val, bool, Weights> * Graph<Val, Weights>::getAllShortestPaths(const Val val, bool isIgnoreWeights) {
    if(this->isWeightsGraph() && !isIgnoreWeights) { //有权且不无视权重
        return getAllShortestPathsInWeightedGraph(val);
    }
    else { //无权
        return getAllShortestPathsInUnweightedGraph(val);
    }
    return nullptr;
}

template<class Val, class Weights>
tuple<Val, Val, bool, Weights> * Graph<Val, Weights>::getAllShortestPathsInUnweightedGraph(const Val val) {
    if(!this->findVal(val)) {
        return nullptr;
    }

    U_L_L i;
    LinkedQueue<Val> queue;
    tuple<Val, Val, bool, Weights> *result = new tuple<Val, Val, bool, Weights>[this->size];//最短路径表
    for(i=0; i<this->size; ++i) {
        get<0>(result[i]) = this->vals[i];
        get<1>(result[i]) = this->vals[i];
        get<2>(result[i]) = false;
        get<3>(result[i]) = 0;
    }

    //起始节点
    U_L_L valIndex = this->getValIndex(val);
    get<2>(result[valIndex]) = true;
    get<3>(result[valIndex]) = 0;
    queue.push(val);
    
    Val currentVal;
    U_L_L currentValIndex;
    while(!queue.isEmpty()) {
        //获取队头元素
        currentVal = queue.pop();
        currentValIndex = this->getValIndex(currentVal);
        //遍历边表，查询所有边尾是currentVal的边
        for(i=0; i<this->size; ++i) {
            if(this->edges[currentValIndex][i] && !get<2>(result[i])) { //获取到边头节点下标，且该节点未遍历过
                //边头节点入队
                queue.push(this->vals[i]);
                //设置最短路径表
                get<1>(result[i]) = currentVal;
                get<2>(result[i]) = true;
                get<3>(result[i]) = get<3>(result[currentValIndex]) + 1;
            }
        }
    }

    return result;
}

template<class Val, class Weights>
tuple<Val, Val, bool, Weights> * Graph<Val, Weights>::getAllShortestPathsInWeightedGraph(const Val val) {
    //Dijkstra算法
    if(!this->findVal(val)) {
        return nullptr;
    }

    U_L_L i;
    PriorityQueue<Val> queue;
    tuple<Val, Val, bool, Weights> *result = new tuple<Val, Val, bool, Weights>[this->size];//最短路径表
    for(i=0; i<this->size; ++i) {
        get<0>(result[i]) = this->vals[i];
        get<1>(result[i]) = this->vals[i];
        get<2>(result[i]) = false;
        get<3>(result[i]) = 0;
    }

    //起始节点
    U_L_L valIndex = this->getValIndex(val);
    get<2>(result[valIndex]) = true;
    get<3>(result[valIndex]) = 0;
    queue.push(val);
    
    Val tempVal;
    Val currentVal;
    U_L_L currentValIndex;
    while(!queue.isEmpty()) {
        //获取队头元素
        currentVal = queue.pop();
        currentValIndex = this->getValIndex(currentVal);
        //遍历边表，查询所有边尾是currentVal的边
        for(i=0; i<this->size; ++i) {
            if(this->edges[currentValIndex][i]) {
                tempVal = get<3>(result[currentValIndex]) + this->edgesWeights[currentValIndex][i];
                if(0 == get<3>(result[i]) || tempVal < get<3>(result[i])) { //获取到边头节点下标，且该节点未遍历过
                    //边头节点入队
                    queue.push(this->vals[i]);
                    //设置最短路径表
                    get<1>(result[i]) = currentVal;
                    get<2>(result[i]) = true;
                    get<3>(result[i]) = get<3>(result[currentValIndex]) + this->edgesWeights[currentValIndex][i];
                }
            }
        }
    }

    return result;
}

//获取最小生成树的算法
template<class Val, class Weights>
tree_node<Val> *Graph<Val, Weights>::prim(Val rootVal) {
    U_L_L i, j, k;
    bool visited[this->size];
    tree_node<Val> *treeNodeArray[this->size];
    for(i=0; i<this->size; ++i) {
        visited[i] = false;
        treeNodeArray[i] = createTree(this->vals[i], (child_tree_list_node<Val> *)nullptr); //将所有值初始化为单个树节点
    }
    visited[this->getValIndex(rootVal)] = true;

    bool flag; //记录当前是不是没遍历到哪怕一个其他端点
    U_L_L tailValIndex, headValIndex; //记录权重最小的边的端点的下标
    Weights minWeights;
    for(i=1; i<this->size; ++i) { //一共只需要遍历size-1次就能创建size个节点的最小生成树
        flag = true;
        minWeights = Unweighted;
        for(j = 0; j<this->size; ++j) { //遍历所有已经遍历过的节点，寻找下一个最短路
            if(visited[j]) {
                for(k = 0; k<this->size; ++k) { //遍历所有以当前节点为尾节点的边的头节点
                    if(j == k) {
                        continue;
                    }
                    if(!visited[k] && this->edges[j][k] && (flag || minWeights > this->edgesWeights[j][k])) {
                        flag = false;
                        //记录当前最小边
                        tailValIndex = j;
                        headValIndex = k;
                        minWeights = this->edgesWeights[j][k];
                    }
                }
            }
        }
        visited[headValIndex] = true;
        insertSubTree(treeNodeArray[tailValIndex], treeNodeArray[headValIndex]);
    }
    return treeNodeArray[this->getValIndex(rootVal)];
}

template<class Val, class Weights>
tree_node<Val> *Graph<Val, Weights>::kruskal(Val rootVal) {
    //因为需要返回目标值为根的最小生成树，传统方法没办法实现，所有用一个图对象保存最小生成树的边，再直接调用prim算法
    U_L_L i, j, k;
    Graph<Val, Weights> minGraph;
    U_L_L visited[this->size];
    for(i=0; i<this->size; ++i) {
        visited[i] = i;
        minGraph.insertVal(this->vals[i]);
    }

    //将所有边塞入优先队列
    PriorityQueue<tuple<Weights, Val, Val>> queue;
    for(i=0; i<this->size; ++i) {
        for(j=0; j<this->size; ++j) {
            if(i == j) {
                continue;
            }

            if(this->edges[i][j]) {
                queue.push(make_tuple(this->edgesWeights[i][j], this->vals[i], this->vals[j]));
            }
        }
    }

    //开始造树
    tuple<Weights, Val, Val> edge;
    U_L_L tailValIndex, headValIndex, tempVisited, num;
    num = 0;
    while(!queue.isEmpty()) {
        edge = queue.pop();
        tailValIndex = this->getValIndex(get<1>(edge));
        headValIndex = this->getValIndex(get<2>(edge));
        if(visited[tailValIndex] != visited[headValIndex]) { //没有记录，不会形成回路
            ++num;
            minGraph.setEdge(get<1>(edge), get<2>(edge), get<0>(edge), GraphRoadTypeUndirected);
            tempVisited = visited[headValIndex];
            for(i=0; i<this->size; ++i) {
                if(visited[i] == tempVisited) {
                    visited[i] = visited[tailValIndex];
                }
            }
            if(num == this->size-1) {
                break;
            }
        }
    }
    return minGraph.prim(rootVal);
}

//获取最大流通量的算法
template<class Val, class Weights>
Weights Graph<Val, Weights>::getMaxFlowFuncTypeNormal(const Val startVal, const Val endVal) {
    U_L_L i, j;
    Weights maxFlow = Unweighted;
    Graph<Val, Weights> residualGraph; //记录所有未满路径和剩余流量
    for(i=0; i<this->size; ++i) {
        residualGraph.insertVal(this->vals[i]);
    }
    for(i=0; i<this->size; ++i) {
        for(j=0; j<this->size; ++j) {
            if(this->edges[i][j]) {
                residualGraph.setEdge(this->vals[i], this->vals[j], this->edgesWeights[i][j], GraphRoadTypeDirected);
            }
        }
    }

    //占用startVal->endVal路径上的所有剩余流量
    pair<DynamicStack<Val>*, Weights> road;
    while(true) {
        //找两节点之间的最短路径（无视路径权重），找不到就退出死循环
        road = residualGraph.getShortestPaths(startVal, endVal, true);

        //遍历子路径，找到最小的剩余流量
        Weights minWeights = Unweighted;
        DynamicStack<Val>* roadValStack = road.first; //[headVal...tailVal]->
        if(nullptr == roadValStack || roadValStack->isEmpty()) {
            break;
        }
        LinkedQueue<pair<Val, Val>> roadQueue; //<tailVal, headVal>
        Val tailVal, headVal;
        tailVal = roadValStack->pop();
        while(!roadValStack->isEmpty()) {
            headVal = roadValStack->pop();
            if(Unweighted == minWeights || minWeights > residualGraph.getEdgeWidghts(tailVal, headVal)) {
                minWeights = residualGraph.getEdgeWidghts(tailVal, headVal);
            }
            roadQueue.push(make_pair(tailVal, headVal));
            tailVal = headVal;
        }

        //重新设置该路径的所有子路径的剩余流量
        pair<Val, Val> childRoad;
        Weights newWeights;
        while(!roadQueue.isEmpty()) {
            childRoad = roadQueue.pop();
            newWeights = Unweighted;
            if(residualGraph.getEdgeWidghts(childRoad.first, childRoad.second) > minWeights) {
                newWeights = residualGraph.getEdgeWidghts(childRoad.first, childRoad.second) - minWeights;
            }
            if(Unweighted == newWeights) { //若剩余流量为0，删除该子路径
                residualGraph.deleteEdge(childRoad.first, childRoad.second, GraphRoadTypeDirected);
            }
            else {
                residualGraph.setEdge(childRoad.first, childRoad.second, newWeights, GraphRoadTypeDirected);
            }
        }

        delete roadValStack;
    }

    //计算最大流量
    U_L_L startIndex = this->getValIndex(startVal);
    for(i=0; i<this->size; ++i) {
        if(i == startIndex) {
            continue;
        }
        if(this->edges[startIndex][i]) {
            //getEdgeWidghts函数遇到不存在边时返回Unweighted，所以不用管边是否存在的问题
            maxFlow += this->edgesWeights[startIndex][i] - residualGraph.getEdgeWidghts(startVal, this->vals[i]);
        }
    }

    return maxFlow;
}

template<class Val, class Weights>
Weights Graph<Val, Weights>::getMaxFlowFuncTypeFordFulkerson(const Val startVal, const Val endVal, PriorityQueue<Val> *S) {
    U_L_L i, j;
    Weights maxFlow = Unweighted;
    Graph<Val, Weights> residualGraph; //记录所有未满路径和剩余流量
    for(i=0; i<this->size; ++i) {
        residualGraph.insertVal(this->vals[i]);
    }
    for(i=0; i<this->size; ++i) {
        for(j=0; j<this->size; ++j) {
            if(this->edges[i][j]) {
                residualGraph.setEdge(this->vals[i], this->vals[j], this->edgesWeights[i][j], GraphRoadTypeDirected);
            }
        }
    }

    //占用startVal->endVal路径上的所有剩余流量
    pair<DynamicStack<Val>*, Weights> road;
    while(true) {
        //找两节点之间的最短路径（无视路径权重），找不到就退出死循环
        road = residualGraph.getShortestPaths(startVal, endVal, true);

        //遍历子路径，找到最小的剩余流量
        Weights minWeights = Unweighted;
        DynamicStack<Val>* roadValStack = road.first; //[headVal...tailVal]->
        if(nullptr == roadValStack || roadValStack->isEmpty()) {
            delete roadValStack;
            break;
        }
        LinkedQueue<pair<Val, Val>> roadQueue; //<tailVal, headVal>
        Val tailVal, headVal;
        tailVal = roadValStack->pop();
        while(!roadValStack->isEmpty()) {
            headVal = roadValStack->pop();
            if(Unweighted == minWeights || minWeights > residualGraph.getEdgeWidghts(tailVal, headVal)) {
                minWeights = residualGraph.getEdgeWidghts(tailVal, headVal);
            }
            roadQueue.push(make_pair(tailVal, headVal));
            tailVal = headVal;
        }

        //重新设置该路径的所有子路径的剩余流量
        pair<Val, Val> childRoad;
        Weights newWeights;
        while(!roadQueue.isEmpty()) {
            childRoad = roadQueue.pop();
            newWeights = 0;
            if(residualGraph.getEdgeWidghts(childRoad.first, childRoad.second) > minWeights) {
                newWeights = residualGraph.getEdgeWidghts(childRoad.first, childRoad.second) - minWeights;
            }
            if(0 == newWeights) { //若剩余流量为0，删除该子路径
                residualGraph.deleteEdge(childRoad.first, childRoad.second, GraphRoadTypeDirected);
            }
            else {
                residualGraph.setEdge(childRoad.first, childRoad.second, newWeights, GraphRoadTypeDirected);
            }
            //添加or设置反向路径
            Weights tempWeight = 0;
            if(residualGraph.findEdge(childRoad.second, childRoad.first, GraphRoadTypeDirected)) {
                tempWeight = residualGraph.getEdgeWidghts(childRoad.second, childRoad.first);
            }
            if(tempWeight+minWeights > 0) {
                residualGraph.setEdge(childRoad.second, childRoad.first, tempWeight+minWeights, GraphRoadTypeDirected);
            }
        }

        delete roadValStack;
    }

    //计算最大流量
    U_L_L startIndex = this->getValIndex(startVal);
    for(i=0; i<this->size; ++i) {
        if(i == startIndex) {
            continue;
        }
        if(this->edges[startIndex][i]) {
            //getEdgeWidghts函数遇到不存在边时返回Unweighted，所以不用管边是否存在的问题
            maxFlow += this->edgesWeights[startIndex][i] - residualGraph.getEdgeWidghts(startVal, this->vals[i]);
        }
    }
    // residualGraph.print();

    //用于最小割的部分
    if(nullptr != S) {
        S->push(startVal);
        U_L_L startValIndex = getValIndex(startVal);
        Val currentVal;
        pair<DynamicStack<Val>*, Weights> path;
        for(i=0; i<this->size; ++i) {
            if(i == startValIndex) {
                continue;
            }
            currentVal = this->vals[i];
            path = residualGraph.getShortestPaths(startVal, currentVal, true);
            if(nullptr != path.first && !((DynamicStack<Val>*)path.first)->isEmpty()) {
                S->push(currentVal);
            }
        }
    }

    return maxFlow;
}

template<class Val, class Weights>
Weights Graph<Val, Weights>::getMaxFlowFuncTypeEdmondsKarp(const Val startVal, const Val endVal) {
    //Edmonds-Karp算法是Ford-Fulkerson算法的变种
    //Ford-Fulkerson算法选择startVal->endVal可以是任意的
    //但是Edmonds-Karp算法要把图当作无权图寻找最短路径
    //由于已实现的Ford-Fulkerson算法就是把图当作无权图寻找最短路径（getShortestPaths的最后一个参数设置为true）
    //所以我们的Ford-Fulkerson算法其实就是Edmonds-Karp算法
    //但还是要注意两者的区别
    return this->getMaxFlowFuncTypeFordFulkerson(startVal, endVal);
}

template<class Val, class Weights>
Weights Graph<Val, Weights>::getMaxFlowFuncTypeDinic(const Val startVal, const Val endVal) {
    U_L_L i, j;
    Weights maxFlow = Unweighted;
    Graph<Val, Weights> residualGraph; //记录所有未满路径和剩余流量
    for(i=0; i<this->size; ++i) {
        residualGraph.insertVal(this->vals[i]);
    }
    for(i=0; i<this->size; ++i) {
        for(j=0; j<this->size; ++j) {
            if(this->edges[i][j]) {
                residualGraph.setEdge(this->vals[i], this->vals[j], this->edgesWeights[i][j], GraphRoadTypeDirected);
            }
        }
    }

    //不断生成levelGraph，并处理residualGraph
    Graph<Val, Weights> levelGraph;
    Graph<Val, Weights> blockingGraph; //记录levelGraph的阻塞流
    pair<DynamicStack<Val>*, Weights> blockingPath; //阻塞路
    LinkedQueue<Val> currentLevelValsQueue; //这一层的节点
    LinkedQueue<Val> nextLevelValsQueue; //下一层的节点
    LinkedQueue<tuple<Val, Val, Weights>> nextLevelEdgesQueue; //本层节点到下层节点的边
    LinkedQueue<Val> blockingValsQueue; //blockingPath的值，<-[startVal...endVal]
    Val currentVal, tempVal;
    U_L_L currentValIndex;
    Weights edgeWeights;
    Weights blockingWeights, tempWeights;
    tuple<Val, Val, Weights> edge;
    pair<DynamicStack<Val> *, Weights> shortesPath = residualGraph.getShortestPaths(startVal, endVal, true);
    int time = 0;
    while(nullptr != shortesPath.first && !((DynamicStack<Val> *)shortesPath.first)->isEmpty()) {
        ++time;
        //生成levelGraph
        levelGraph.clean();
        currentLevelValsQueue.push(startVal);
        int time2 = 0;
        while(!currentLevelValsQueue.isEmpty()) { //这一层节点不为空,证明还没遍历到endVal
            ++time2;
            while(!currentLevelValsQueue.isEmpty()) { //这层循环判断虽然与上一层相同，但这一层是为了找寻下一层节点，并填充levelGraph
                if(currentLevelValsQueue.getSize() > MAX_SIZE) {
                    return maxFlow;
                }
                currentVal = currentLevelValsQueue.pop();
                //填入levelGraph
                levelGraph.insertVal(currentVal);
                //因为residualGraph一开始是一比一复制this且中间没有删除节点的操作，所以可以用本地方法，实际上找的还是在residualGraph中vals的下标
                currentValIndex = this->getValIndex(currentVal);
                //查找所有currentVal为起点的边
                for(i=0; i<this->size; ++i) {
                    if(currentValIndex == i) {
                        continue;
                    }
                    tempVal = this->vals[i];
                    //如果找到边且这个当前的箭头节点(tempVal)不存在于levelGraph上，就当作下一层节点处理,并将该边记录在levelGraph里
                    if(!levelGraph.findVal(tempVal) && residualGraph.findEdge(currentVal, tempVal, GraphRoadTypeDirected)) {
                        edgeWeights = residualGraph.getEdgeWidghts(currentVal, tempVal);
                        nextLevelValsQueue.push(tempVal);
                        nextLevelEdgesQueue.push(make_tuple(currentVal, tempVal, edgeWeights));
                    }
                }
            }
            //将原本下一层的节点和边放进levelGraph中
            while(!nextLevelValsQueue.isEmpty()) {
                tempVal = nextLevelValsQueue.pop();
                levelGraph.insertVal(tempVal);
                currentLevelValsQueue.push(tempVal);
            }
            while(!nextLevelEdgesQueue.isEmpty()) {
                edge = nextLevelEdgesQueue.pop();
                levelGraph.setEdge(get<0>(edge), get<1>(edge), get<2>(edge), GraphRoadTypeDirected);
            }
        }

        //在levelGraph寻找阻塞流，然后将流以反方向汇入residualGraph中
        blockingGraph.clean();
        blockingPath = levelGraph.getShortestPaths(startVal, endVal, true);
        while(nullptr != blockingPath.first && !((DynamicStack<Val> *)blockingPath.first)->isEmpty()) {
            //获取阻塞流所有节点到，并塞入blockingGraph中，并查找阻塞权重
            blockingWeights = 0;
            currentVal = ((DynamicStack<Val>*)blockingPath.first)->pop();
            blockingValsQueue.push(currentVal);
            while(!((DynamicStack<Val>*)blockingPath.first)->isEmpty()) {
                tempVal = ((DynamicStack<Val>*)blockingPath.first)->pop();
                blockingValsQueue.push(tempVal);
                blockingGraph.insertVal(currentVal);
                blockingGraph.insertVal(tempVal);
                if(0 == blockingWeights || blockingWeights > levelGraph.getEdgeWidghts(currentVal, tempVal)) {
                    blockingWeights = levelGraph.getEdgeWidghts(currentVal, tempVal);
                }
                currentVal = tempVal;
            }

            //blockingGraph设置阻塞流，levelGraph设置剩余流，residualGraph设置反向流与剩余流
            currentVal = blockingValsQueue.pop();
            while(!blockingValsQueue.isEmpty()) {
                tempVal = blockingValsQueue.pop();
                
                tempWeights = 0;
                if(blockingGraph.findEdge(currentVal, tempVal, GraphRoadTypeDirected)) {
                    tempWeights = blockingGraph.getEdgeWidghts(currentVal, tempVal);
                }
                if(tempWeights+blockingWeights > 0) {
                    blockingGraph.setEdge(currentVal, tempVal, tempWeights+blockingWeights, GraphRoadTypeDirected); //设置阻塞流
                    residualGraph.setEdge(tempVal, currentVal, tempWeights+blockingWeights, GraphRoadTypeDirected); //设置反向流
                }

                tempWeights = levelGraph.getEdgeWidghts(currentVal, tempVal);
                if(tempWeights <= blockingWeights) { //没剩余的就删除
                    levelGraph.deleteEdge(currentVal, tempVal, GraphRoadTypeDirected);
                    residualGraph.deleteEdge(currentVal, tempVal, GraphRoadTypeDirected);
                }
                else { //设置剩余流
                    levelGraph.setEdge(currentVal, tempVal, tempWeights-blockingWeights, GraphRoadTypeDirected);
                    residualGraph.setEdge(currentVal, tempVal, tempWeights-blockingWeights, GraphRoadTypeDirected);
                }

                currentVal = tempVal;
            }

            delete blockingPath.first;
            //继续获取阻塞流
            blockingPath = levelGraph.getShortestPaths(startVal, endVal, true);
        }
        delete blockingPath.first;
        delete shortesPath.first;
        shortesPath = residualGraph.getShortestPaths(startVal, endVal, true);
    }
    delete shortesPath.first;

    //计算最大流
    currentValIndex = this->getValIndex(startVal);
    for(i=0; i<this->size; ++i) {
        if(i == currentValIndex) {
            continue;
        }
        tempVal = this->vals[i];
        if(this->edges[currentValIndex][i]) {
            if(residualGraph.findEdge(startVal, tempVal, GraphRoadTypeDirected)) {
                maxFlow += this->edgesWeights[currentValIndex][i] - residualGraph.getEdgeWidghts(startVal, tempVal);
            }
            else {
                maxFlow += this->edgesWeights[currentValIndex][i];
            }
        }
    }

    return maxFlow;
}

//最大匹配算法
template<class Val, class Weights>
Weights Graph<Val, Weights>::MCBM(Val *U, U_L_L uSize, Val *V, U_L_L vSize) {
    //创建新的图，利用最大流算法获取匹配值
    U_L_L i, j;
    Graph<Val, Weights> G;
    Val startVal = U[0], endVal = V[0], currentVal;
    U_L_L currentValIndex;
    for(i=0; i<uSize; ++i) {
        G.insertVal(U[i]);
    }
    for(i=0; i<vSize; ++i) {
        G.insertVal(V[i]);
    }
    while(G.findVal(startVal)) {
        ++startVal;
    }
    G.insertVal(startVal);
    while(G.findVal(endVal)) {
        ++endVal;
    }
    G.insertVal(endVal);
    for(i=0; i<uSize; ++i) {
        currentVal = U[i];
        G.setEdge(startVal, currentVal, 1, GraphRoadTypeDirected);
    }
    for(i=0; i<vSize; ++i) {
        currentVal = V[i];
        G.setEdge(currentVal, endVal, 1, GraphRoadTypeDirected);
    }
    for(i=0; i<uSize; ++i) {
        currentVal = U[i];
        currentValIndex = this->getValIndex(currentVal);
        for(j=0; j<this->size; ++j) {
            if(this->edges[currentValIndex][j]) {
                G.setEdge(currentVal, this->vals[j], 1, GraphRoadTypeDirected);
            }
        }
    }

    return G.getMaximunFlow(startVal, endVal, GetMaximunFlowFuncTypeFordFulkerson);
}

template<class Val, class Weights>
Weights Graph<Val, Weights>::hungarian(Val *U, U_L_L uSize, Val *V, U_L_L vSize, bool getMax) {
    U_L_L i, j, k;
    bool isContinue, isOnlyOne, isFind;
    LinkedQueue<pair<U_L_L, U_L_L>> matchs;
    pair<U_L_L, U_L_L> theMatch;
    Val theU, theV;
    Weights minWeights, maxWeights = 0, maxMatching = 0;
    Weights theMatrix[uSize][vSize]; //保存U和V两个集合节点间的路径权重
    int theLine[uSize][vSize]; //记录每行每列的覆盖0的线，每一条线穿过一个格子，这个格子里的数量+1（同时也记录最后过滤了哪些行与列的值）
    int lineNum;

    //找到最大值
    for(i=0; i<uSize; ++i) {
        for(j=0; j<vSize; ++j) {
            if(maxWeights < this->getEdgeWidghts(U[i], V[j])) {
                maxWeights = this->getEdgeWidghts(U[i], V[j]);
            }
        }
    }

    //初始化匹配矩阵
    for(i=0; i<uSize; ++i) {
        for(j=0; j<vSize; ++j) {
            if(this->findEdge(U[i], V[j], GraphRoadTypeUndirected)) {
                theMatrix[i][j] = ((getMax)?(-1):(1))*this->getEdgeWidghts(U[i], V[j]);
            }
            else {
                theMatrix[i][j] = maxWeights;
            }
        }
    }
    
    //每一列每一行都起码有一个0
    for(i=0; i<uSize; ++i) {
        //找到第i行的最小值
        minWeights = theMatrix[i][0];
        for(j=0; j<vSize; ++j) {
            if(minWeights > theMatrix[i][j]) {
                minWeights = theMatrix[i][j];
            }
        }
        //若当前行不存在0，则让第i行所有值减去最小值，确保当前行存在0
        if(0 != minWeights) {
            for(j=0; j<vSize; ++j) {
                theMatrix[i][j] -= minWeights;
            }
        }
    }
    for(j=0; j<vSize; ++j) {
        //找到第j列的最小值
        minWeights = theMatrix[0][j];
        for(i=0; i<uSize; ++i) {
            if(minWeights > theMatrix[i][j]) {
                minWeights = theMatrix[i][j];
            }
        }
        //若当前列不存在0，则让第j列所有值减去最小值，确保当前行存在0
        if(0 != minWeights) {
            for(i=0; i<uSize; ++i) {
                theMatrix[i][j] -= minWeights;
            }
        }
    }

    while(true) {
        //清空线
        lineNum = 0;
        for(i=0; i<uSize; ++i) {
            for(j=0; j<vSize; ++j) {
                theLine[i][j] = 0;
            }
        }
        //划线覆盖0
        for(i=0; i<uSize; ++i) {
            for(j=0; j<vSize; ++j) {
                //在同一行和同一列中找第二个0，有的话就往该方向划线，否则只需要随便画一条（默认竖线）
                if(0 != theMatrix[i][j] || 0 != theLine[i][j]) {
                    continue;
                }

                //在同一行找0，找到就画横向线
                isFind = false;
                for(k=j+1; k<vSize; ++k) {
                    if(0 != theMatrix[i][k] || 0 != theLine[i][j]) {
                        continue;
                    }
                    isFind = true;
                    //横向
                    ++lineNum;
                    for(k=0; k<vSize; ++k) { //这里直接用k也可以，遍历完这里上一层循环也没办法继续遍历了，相当于这一行不用再找0了
                        ++theLine[i][k];
                    }
                }

                //如果已经画了横线了就没必要画竖线啦
                if(isFind) {
                    continue;
                }

                //竖向
                ++lineNum;
                for(k=0; k<uSize; ++k) {
                    ++theLine[k][j];
                }
            }
        }

        //打印每一轮循环的重要讯息
        // debugOut << "lineNum" << endl;
        // cout << lineNum << endl;
        // debugOut << "theMatrix" << endl;
        // for(i=0; i<uSize; ++i) {
        //     cout  << "[ ";
        //     for(j=0; j<vSize; ++j) {
        //         cout << theMatrix[i][j] << ' ';
        //     }
        //     cout  << "]" << endl;
        // }
        // debugOut << "theLine" << endl;
        // for(i=0; i<uSize; ++i) {
        //     cout  << "[ ";
        //     for(j=0; j<vSize; ++j) {
        //         cout << theLine[i][j] << ' ';
        //     }
        //     cout  << "]" << endl;
        // }
        
        if(lineNum == ((uSize <= vSize)?(uSize):(vSize))) {
            //终止循环
            break;
        }

        //找到没被线覆盖的区域的最小值
        minWeights = 0;
        for(i=0; i<uSize; ++i) {
            for(j=0; j<vSize; ++j) {
                if(0 == theLine[i][j] && (0 == minWeights || minWeights > theMatrix[i][j])) {
                    minWeights = theMatrix[i][j];
                }
            }
        }
        //将没被线覆盖的区域的值减去这个最小值
        for(i=0; i<uSize; ++i) {
            for(j=0; j<vSize; ++j) {
                if(0 == theLine[i][j]) {
                    theMatrix[i][j] -= minWeights;
                }
                else if(1 < theLine[i][j]) {
                    theMatrix[i][j] += minWeights;
                }
            }
        }
    }

    //theMatrix会存在若干个0，匹配边从这些0里选
    for(i=0; i<uSize; ++i) {
        for(j=0; j<vSize; ++j) {
            theLine[i][j] = 0;
        }
    }
    //先找那些当前行或者列只有自己一个0的（不包括过滤了的），这种就必须要选
    for(i=0; i<uSize; ++i) {
        for(j=0; j<vSize; ++j) {
            if(0 != theMatrix[i][j] || 0 != theLine[i][j]) {
                continue;
            }

            isOnlyOne = false;

            //行
            for(k=j+1; k<vSize; ++k) {
                if(0 == theMatrix[i][k]) {
                    break;
                }
            }
            if(k==vSize) { //上一层循环跑完了都没找到第二个0
                isOnlyOne = true;
            }
            else {
                //列
                for(k=i+1; k<uSize; ++k) {
                    if(0 == theMatrix[k][j]) {
                        break;
                    }
                }
                if(k==uSize) { //上一层循环跑完了都没找到第二个0
                    isOnlyOne = true;
                }
            }

            //如果现在这个0是天选之人，那就只能选它了
            if(isOnlyOne) {
                //保存匹配边
                matchs.push(make_pair(i, j));
                //过滤和该边的两节点有关的所有边
                for(k=0; k<vSize; ++k) { //行
                    theLine[i][k] = 1;
                }
                for(k=0; k<uSize; ++k) { //竖
                    theLine[k][j] = 1;
                }
            }
        }
    }
    //从剩余的0里随便选，注意要过滤就行了
    for(i=0; i<uSize; ++i) {
        for(j=0; j<vSize; ++j) {
            if(0 != theMatrix[i][j] || 0 != theLine[i][j]) {
                continue;
            }

            //保存匹配边
            matchs.push(make_pair(i, j));
            //过滤和该边的两节点有关的所有边
            for(k=0; k<vSize; ++k) { //行
                theLine[i][k] = 1;
            }
            for(k=0; k<uSize; ++k) { //竖
                theLine[k][j] = 1;
            }
        }
    }

    //计算匹配值
    while(!matchs.isEmpty()) {
        theMatch = matchs.pop();
        theU = U[theMatch.first];
        theV = V[theMatch.second];
        maxMatching += this->getEdgeWidghts(theU, theV);
    }
    
    return maxMatching;
}

//解决稳定婚配问题的算法
template<class Val, class Weights>
LinkedQueue<pair<Val, Val>> *Graph<Val, Weights>::GaleShapley(Val *mans, LinkedQueue<Val> *mansLike, U_L_L manNum, Val *womans, StaticList<Val> *womansLike, U_L_L womanNum) {
    U_L_L i, j, womanIndex, husbandIndex, manPower, husbandPower;
    LinkedQueue<pair<Val, Val>> *result = new LinkedQueue<pair<Val, Val>>;
    int manMarryState[manNum] = {0}; //记录所有男性婚姻状态：0-未婚；1-已婚；3-找不到对象
    pair<bool, Val> womanMarryState[womanNum]; //记录所有女性的婚姻状态：<是否已婚，丈夫是谁>

    //初始化参数
    for(i=0; i<womanNum; ++i) {
        womanMarryState[i].first = false;
    }

    while(true) { //死循环直到所有男的要不已婚要不就是找不到对象
        //遍历每一个未婚男
        for(i=0; i<manNum; ++i) {
            if(1 == manMarryState[i] || 3 == manMarryState[i]) {
                continue;
            }

            //获取当前man最喜欢的woman
            Val woman = mansLike[i].pop();
            for(j=0; j<womanNum; ++j) {
                if(woman == womans[j]) {
                    womanIndex = j;
                }
            }

            //获取woman的结婚状态，两种状态两种处理方式：
            //未婚：直接结婚
            //已婚：对比现在的man和自己丈夫谁更好，man更好则出轨，否则不理man
            if(womanMarryState[womanIndex].first) { //已婚
                //找出women心中man和丈夫的“战斗力”（j越小“战斗力越强”）
                for(j=0; j<womansLike[womanIndex].getSize(); ++j) {
                    if(mans[i] == womansLike[womanIndex].getVal(j)) { //man
                        manPower = j;
                    }
                    else if(womanMarryState[womanIndex].second == womansLike[womanIndex].getVal(j)) { //丈夫
                        husbandPower = j;
                    }
                }

                if(manPower < husbandPower) { //man比丈夫强
                    //找到目前丈夫下标
                    for(j=0; j<manNum; ++j) {
                        if(womanMarryState[womanIndex].second == mans[j]) {
                            husbandIndex = j;
                        }
                    }
                    
                    manMarryState[husbandIndex] = mansLike[husbandIndex].isEmpty()?3:0;
                    womanMarryState[womanIndex].second = mans[i];
                    manMarryState[i] = 1;
                }
                else if(mansLike[i].isEmpty()) { //man比丈夫弱，且man的候选名单里没人了，证明这个man找不到对象了
                    manMarryState[i] = 3;
                }
            }
            else { //未婚
                womanMarryState[womanIndex].first = true;
                womanMarryState[womanIndex].second = mans[i];
                manMarryState[i] = 1;
            }
        }

        //检查是否满足条件跳出死循环
        for(i=0; i<manNum; ++i) {
            if(0 == manMarryState[i]) {
                break;
            }
        }
        if(i == manNum) {
            break;
        }
    }

    //获取所有结婚对象，从woman里找
    for(i=0; i<womanNum; ++i) {
        if(!womanMarryState[i].first) { //未婚跳过
            continue;
        }

        result->push(make_pair(womanMarryState[i].second, womans[i]));
    }

    return result;
}

}

#endif